Міністерство освіти та науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
з лабораторної роботи № 2
З дисципліни: „Системи штучного інтелекту”
На тему: „ Використання евристичної функції для створення гри ”
Виконав:
ст. гр. КСМ-5
Львів 2007
Мета роботи: Cтворення зразку евристичної функції, яка описує стан укладанки, що полягає у складанні в зростаючому порядку цифр від 1 до 8. Створений алгоритм має за мету розв’язання гри при мінімально можливій кількості кроків, а також розпізнавання станів, у яких гра не має розв’язку. Початковий стан гри встановлюється випадковим чином. Головними елементами евристичної функції є складові підрахунку відстаней вибраних елементів від їх попереднього місця.
Теоретичні відомості
Алгоритм гри є простим і базується на 3 засадах:
Підраховане значення евристичної функції відбиває єдиний можливий крок, що залежить від розташування нульового елементу і для якого значення функції є мінімальним (нескінченне від біжучого значення функції)
Не варто повторювати попередній крок, якщо він призводить до заплутування алгоритму, і відповідно, не скорочує кількість кроків
Нульове значення евристичної функції означає, що даний стан гри є кінцевим станом (елементи є укладеними або їх укладання є неможливим)
Стан гри описаний N*N-елементною таблицею Tab[*] цілих цифр в полях пронумерованих від 0 до N*N
Приймемо наступну послідовність алгоритму:
Етап 1
Початковою метою гри є уставляння одиниці на першому місці (в таблиці це поле з номером 0). Відповідно, цей порядок повинен мати найбільший приоритет, тобто йому має відповідати складова, що має найбільшу вагу в моделі функції. Ось ця складова:
wartosc+=1000000*abs(miejsce[1]%3-szukana%3);
//розглядання нормованої метрики по горизонталі
wartosc+=1000000*abs(miejsce[1]/3-szukana/3);
//розглядання нормованої метрики по вертикалі
Де значення змінної szukana в цей момент дорівнює 0.
Найбільша вага цієї складової у зразку евристичної функції доводить, що цей елемент ніколи не буде пересунуто зі свого місця.
На цьому етапі гри нульове поле прагне до нульового місця таблиці елементів
Етап 2
Наступний крок полягає у встановленні 2 і 3 на свої місця. Очевидно евристична функція намагається встановити їх відповідно стану:
1
_
2
х
x
3
х
x
х
Де х означає поле замін перед випадковим укладанням залишкових цифр 4,5,6,7,8
Цей етап описує наступний фрагмент коду:
Елемент 2 має більшу вагу ніж 3, і його варто поставити на власну позицію першим. На цьому етапі нульове поле прагне до першого елементу таблиці.
тобто значення змінної szukana буде зараз 1.
Зауважимо, що у момент гри представлений вище, не має можливості виконання іншого кроку, як відправлення 2 і 3 на свої місця. Це виникає з початкових умов (не можна повернутись) і окрім цього алгоритм забезпечує, що одиниця лишається на свому місці.
Очевидно, що потрібно забезпечити перед досягненням нуля евристичною функцією (що призвело би до закінчення алгоритму на цьому етапі) привласнити їй числове значення
if (Tab[0]==1 && Tab[2]==2 && Tab[5]==3) wartosc+=30;
Після встановлення 2 і 3 на власні місця мусимо скорегувати значення евристичної функції у 110000, що реалізує наступний код:
if (Tab[0]==1 && Tab[1]==2 && Tab[2]==3)
//після встановлення 2 i 3 на місця
{
szukana=3;
wartosc-=110000;
}
Алгоритм забезпечує пересування нульового елементу в таблиці до поля з номером 3, що є необхідним при переході до наступного етапу гри.
Етап 3
На цьому етапі, що є подібним до етапу 2, займемося 4 і 7. Хочемо прийти до наступного стану гри:
1
2
3
_
x
x
4
7
x
Де х означає поле, що можна заміняти перед випадковим укладанням залишених цифр 5, 6, 8.
Елемент 4 має вищу вагу ніж 7, тому його слід поставити на власну позицію першим. На цьому етапі нульове поле прагне до третього елементу таблиці (встановлений в кінці етапу 2).
Тобто значення змінної зараз буде 3.
Подібно, як у етапі 2 зауважимо, що у момент гри, представлений вище, алгоритм не має можливості виконання...
